package com.gjh.study.algorithm4.sort;

import edu.princeton.cs.algs4.StdOut;

public class Shell extends SortBase {
    @Override
    public void sort(Comparable[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3) {
            h = 3 * h + 1;
        }
        // StdOut.println("h=" + h);
        // StdOut.print("排序前：\t");
        // show(a);
        while (h >= 1) {
            // StdOut.printf("h=%d \t", h);
            for (int i = h; i < N; i++) {
                // StdOut.printf("i=%d \t", i);
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    // StdOut.printf("内循环：\t\th=%d\ti=%d\tj=%d\t", h, i, j);
                    exch(a, j, j - h);
                    // StdOut.print("内循环：\t");
                    // show(a);
                }
                // StdOut.printf("中间循环：\th=%d\ti=%d\t\t\t", h, i);
                // show(a);
            }
            // StdOut.printf("外循环：\th=%d\t\t\t\t\t\t", h);
            // show(a);
            h = h / 3;
        }
        // StdOut.print("排序结果：\t");
        // show(a);
    }
}
